/**
 * 
 */
package edu.umd.clip.lm.model;

import edu.umd.clip.lm.util.*;
/**
 * @author Denis Filimonov <den@cs.umd.edu>
 *
 */
public class ProbTree implements AbstractProbTree, Cloneable {
	protected BinaryPrefix prefix;

	static final double MIN_TREE_PROB = 1E-10;
	double scale;
	DecoderCompactProbTree tree;
	boolean readonly = false;
	
	/**
	 * Constructs a probability tree of s single tuple (used for <s>)
	 * @param tuple
	 */
	public ProbTree() {
		this(new BinaryPrefix(0));
	}
	
	public ProbTree(BinaryPrefix prefix) {
		scale = 1.0;
		tree = DecoderCompactProbTree.getSingleNodeTree();
		this.prefix = prefix;		
	}
	/**
	 * @param overtFactors
	 * @param prefix
	 * @param logScale
	 */
	private ProbTree(BinaryPrefix prefix, double scale) {
		this.prefix = prefix;
		this.scale = scale;
	}

	public ProbTree compact() {
		ProbTree t = new ProbTree(prefix, scale);
		t.tree = tree == null ? null : tree.compact();
		return t;
	}
	
	public ProbTree(DecoderCompactProbTree t) {
		this();
		tree = t;
	}

	public static ProbTree makeProbTree(OnDiskCompactProbTree leafy) {
		long start = Timing.nanoTime();
		try {
			DecoderCompactProbTree tree = (DecoderCompactProbTree) DecoderCompactProbTree.getEmptyTree().clone();
			Experiment exp = Experiment.getInstance();
			//FactorTupleDescription desc = exp.getTupleDescription();
			
			int compactFactors[] = leafy.getCompactHiddenFactors();
			float probabilities[] = leafy.getProbabilities();
			for(int i=0; i<leafy.getSize(); ++i) {
				tree.addProbability(exp.getPrefixByCompact(compactFactors[i]), probabilities[i]);
			}
			
			ProbTree probTree = new ProbTree(tree);
			probTree.scale = leafy.getScale();
			return probTree;
		} finally {
			long end = Timing.nanoTime();
			totalCompactifyingTime += end - start;
		}
	}
	
	public static ProbTree makeProbTreeNew(OnDiskCompactProbTree leafy) {
		long start = Timing.nanoTime();
		try {
			DecoderCompactProbTree tree = new DecoderCompactProbTree(DecoderCompactProbTree.getEmptyTree().getSize());
			Experiment exp = Experiment.getInstance();
			//FactorTupleDescription desc = exp.getTupleDescription();
			
			int compactFactors[] = leafy.getCompactHiddenFactors();
			float probabilities[] = leafy.getProbabilities();
			for(int i=0; i<leafy.getSize(); ++i) {
				tree.addProbability(exp.getPrefixByCompact(compactFactors[i]), probabilities[i]);
			}
			
			ProbTree probTree = new ProbTree(tree.trimToSize());
			probTree.scale = leafy.getScale();
			return probTree;
		} finally {
			long end = Timing.nanoTime();
			totalCompactifyingTime += end - start;
		}		
	}
	
	public static long totalLeafyMergeTime = 0;
	public static long totalLeafyMergeCount = 0;
	public static long totalCompactMergeTime = 0;
	public static long totalCompactMergeCount = 0;
	public static long totalCloningTime = 0;
	public static long totalMergingCount = 0;
	public static long totalCompactifyingTime = 0;

	
	/**
	 * tests whether how the cuttingPrefix will cut the tree
	 * @param cuttingPrefix
	 * @return TRUE if the tree is a subtree of the cuttingPrefix, 
	 *         FALSE if there's no intersection between the tree and cuttingPrefix,
	 *         null if the cuttingPrefix can cut the tree (the intersection may still be empty because of pruning)  
	 */
	public Boolean testCut(BinaryPrefix cuttingPrefix) {
		if (cuttingPrefix.isPrefixOf(prefix)) {
			return Boolean.TRUE;
		}
		if (!prefix.isPrefixOf(cuttingPrefix)) {
			return Boolean.FALSE;
		}
		if (tree.findNode(cuttingPrefix.getSuffix(prefix.getSize())) == DecoderCompactProbTree.NO_LINK) {
			return Boolean.FALSE;
		}
		return null;
	}
	/**
	 * Chops a subtree identified by cuttingPrefix off the ProbTree
	 * @param cuttingPrefix
	 * @return the subtree cut, null if nothing has been cut, returns this if all leaves are cut
	 */
	public ProbTree cut(BinaryPrefix cuttingPrefix) {
		DecoderCompactProbTree myTree = tree.getCompactProbTree();
		if (readonly) {
			tree = myTree.copy();
			myTree = tree.getCompactProbTree();
			readonly = false;
		}
		DecoderCompactProbTree cutTree = myTree.cut(cuttingPrefix.getSuffix(prefix.getSize()));
		if (cutTree == null || cutTree.getTotalProb() < ProbMath.MIN_FLOAT_PRECISION) return null;
		if (myTree == cutTree || myTree.getTotalProb() < ProbMath.MIN_FLOAT_PRECISION) {
			//the prefix cut off all leaves from the tree 
			this.tree = cutTree;
			this.prefix = cuttingPrefix;
			return this;
		}
		ProbTree subTree = new ProbTree(cuttingPrefix, scale);
		subTree.tree = cutTree;
		return subTree;
	}
	
	/* (non-Javadoc)
	 * @see java.lang.Object#clone()
	 */
	@Override
	public Object clone() {
		ProbTree copy = new ProbTree(prefix, scale);
		copy.tree = (DecoderCompactProbTree) tree.clone();
		/*
		if (cuts != null) {
			copy.cuts = (HashSet<BinaryPrefix>) cuts.clone();
		}
		*/
		return copy;
	}

	public ProbTree copy() {
		ProbTree copy = new ProbTree(prefix, scale);
		//copy.tree = tree.getCompactProbTree().copy();
		copy.tree = tree;
		readonly = true;
		copy.readonly = true;
		/*
		if (cuts != null) {
			copy.cuts = (HashSet<BinaryPrefix>) cuts.clone();
		}
		*/
		return copy;
	}

	/**
	 * @return the prefix
	 */
	public BinaryPrefix getPrefix() {
		return prefix;
	}

	/* (non-Javadoc)
	 * @see edu.umd.clip.lm.questions.AbstractProbTree#getRoot()
	 */
	public BinaryPrefix getRoot() {
		return prefix;
	}

	/**
	 * @return the logScale
	 */
	public double getScale() {
		return scale;
	}
	
	public double getTreeProb() {
		return tree.getTotalProb();
	}

	public double getTotalProb() {
		return getTreeProb() * scale;
	}
	
	public void scale(double scale) {
		this.scale *= scale;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		long temp;
		temp = Double.doubleToLongBits(scale);
		result = prime * result + (int) (temp ^ (temp >>> 32));
		result = prime * result + ((tree == null) ? 0 : tree.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (!(obj instanceof ProbTree))
			return false;
		ProbTree other = (ProbTree) obj;
		if (!prefix.equals(other.prefix))
			return false;
		if (scale != other.scale)
			return false;
		
		return tree.equals(other.tree);
	}

	public ProbTree getProbTree() {
		return this;
	}
	
}
